The present invention generally relates to flash memory devices. More particularly, this invention relates to a method of maintaining write performance on a NAND flash memory-based solid state drive by shuffling blocks in and out of an over-provisioning pool and proactively erasing blocks containing invalid data.
As known in the art, flash memory is a type of nonvolatile solid-state memory technology. Flash memory components store information in an array of floating-gate transistors (FGTs), referred to as cells. NAND flash cells are organized in what are commonly referred to as pages, which in turn are organized in predetermined sections of the component referred to as memory blocks. Each cell of a NAND flash memory component has a top or control gate (CG) and a floating gate (FG), the latter being sandwiched between the control gate and the channel of the cell. The floating gate is separated from the control gate by an oxide layer and from the channel by another oxide layer, referred to as the tunnel oxide. Data are stored in a NAND flash cell in the form of a charge on the floating gate which, in turn, defines the channel properties of the NAND flash cell by either augmenting or opposing the charge of the control gate. The process of programming (writing 0's to) a NAND cell requires applying a programming charge to the floating gate by applying a programming voltage to the control gate via the word lines. The control gate exerts a Fowler-Nordheim (FN) field that causes the injection of electrons into the floating gate by quantum mechanical tunneling, that is, drawing electrons from the substrate towards the positive charge present in the word line until they reach the floating gate. The process of erasing (writing 1's to) a NAND cell requires removing the programming charge from the floating gate by applying an erase voltage to the device substrate via the bit line. The substrate exerts a Fowler-Nordheim field that pulls electrons from the floating gate to deplete the floating gate of any program charge. Data are stored and retrieved on a page-by-page basis and erased on a block-by-block basis.
NAND flash memory-based solid state drives (SSDs) are becoming the storage media of choice for personal computers. However, NAND flash memory has certain peculiarities that require attention in order to prevent degradation of their performance. A specific example is the ability to maintain the write performance on a NAND flash memory-based SSD.
The change in charge distribution of the floating gate augments or counteracts any voltage applied to the control gate. The potential needed to turn “ON” the gate is subsequently used as the bit value of the cell sensed at any given read. Even though, in NAND flash memory, cells need to be programmed sequentially, that is, all cells within a given daisy chain of FGTs (typically thirty-two) must be programmed sequentially, programming and subsequent verification occurs on a per bit level. The application of a programming voltage by the word lines can only inject electrons into the floating gate. Therefore, the direction of programming can only go from a fully erased state to a fully programmed state, but not vice versa.
In order to erase NAND memory cells, the entire bit line needs to be connected to a 20V erase voltage, which causes current to flow through the entire daisy chain of FGTs and induce Fowler-Nordheim quantum mechanical tunneling between the entire bit line comprising the source and drain of all daisy-chained FGTs and the floating gates of the same FGTs, thereby inducing electron depletion of the floating gates.
As noted above, the fully-erased state of a NAND flash memory cell is a “1.” Programming can only shift cells to a lower value. In the case of multilevel cell (MLC) flash memory that uses, for example, four different levels to encode two bits per cell, possible values are “11” (fully erased), “10,” “01” and “00” (fully programmed). However, as mentioned above, programming in the opposite direction is not possible.
Because of the unidirectional programming of flash memory, it is not possible to overwrite data, in contrast to rotatable media hard disk drives (HDDs) or other volatile and non-volatile memory devices. Instead, the media must be fully erased before it can be reprogrammed. From an operational standpoint of a mass storage device, this limitation poses certain difficulties in that data cannot be updated, but instead must be completely rewritten. Because of the specific architecture of NAND flash and also in order to avoid erase latency, the rewriting of data entails writing the updated data to a previously erased block of NAND flash memory, which is typically a different physical block address than the original block. The block containing the previous data is flagged as invalid, which for all practical purposes is equivalent to no longer having data to the file system. However, this block cannot be rewritten until it is completely erased. Over time, such a rewrite routine will result in the majority of blocks being used, but containing invalid data. The term “used” is employed in this context to designate blocks containing invalid data, as opposed to “occupied” blocks that contain valid data. Used blocks require an erase cycle before new data can be written to them. As a result, the drive's write performance slows down significantly.
A known workaround for the used vs. occupied block issue is the implementation of garbage collection and TRIM commands, which are tools for consolidating valid data and then proactively erasing blocks with obsolete data. In this context, it is important to note that as many blocks as possible have to be in the “erased state” in order to allow fast write access. In short, TRIM (not an acronym) is an ATA-command added to and initiated on the level of the operating system, and a TRIM command may result in the contents of a drive being read into main memory, followed by analysis of valid vs. invalid data, subsequent write-back of the valid data to the drive, and purging of invalid data. Because of wear leveling, the data are typically written to different physical blocks of NAND flash memory. All blocks, the contents of which are read into memory, are erased or scheduled for erase when the data are written back. The net goal of the TRIM operation is that all data contained in any block are valid and used blocks containing invalid data are proactively recycled into the pool of erased, that is, immediately programmable blocks. Moreover, garbage collection in combination with TRIM offers to coalesce data fragments before they are written back to the non-volatile memory in a pattern to maximize occupancy of the blocks.
As can be appreciated from the above, the execution of a TRIM command requires reading out all contents of a flash memory area to be “trimmed” to the system memory, regardless of whether the data are meaningful or just left over on used blocks. TRIM is currently implemented on Microsoft Windows® 7 operating systems, which exist in 32-bit and 64-bit variations. In order to minimize variability and maximize compatibility and portability of drives between different systems running either 32-bit or 64-bit operating systems (OS), it appears advantageous to use a single form of TRIM regardless of the OS version used in any given case. Given the fact that the data need to be shadowed in system memory and that the limitation of the user-addressable memory space is 2 GB in Microsoft's 32-bit operating systems, any single instance of execution of a TRIM command cannot exceed 2 GB of non-volatile memory space from a solid state drive.
An additional drawback of an execution of the TRIM command is that it ties up substantial amounts of system resources with respect to interconnects as well as available system memory space. Therefore, TRIM command executions need to run in the background during idle phases of the system. Still, all of these drawbacks are negligible in view of the write performance maintenance of solid state drives. However, alternative methods could also be employed in order to proactively erase used but not-occupied blocks and, thus, maintain write performance of a solid state drive.